package net.zjitc.tree;

public class Demo {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,6,7,8,9};
        int key = 5;
        int index = serach(arr,key);
        System.out.println(index);
    }

    /**
     * 返回下标
     * @param arr
     * @param key
     * @return 成功：下标  失败：-1
     */
    private static int serach(int[] arr, int key) {
        int left,right,mid;
        left = 0;
        right = arr.length-1;
        while (right>=left){
            mid = (left+right)/2;
            if (arr[mid]>key){ //一定在前半断
               right = mid-1;
            }else if (arr[mid] < key){ //一定在后半断
               left = mid+1;
            }else { //找到了
                return mid;
            }
        }
        return -1;
    }
}
